package kmp;

public class FindAllGoodStrings {

    public static int MOD = 10_0000_0007;

    public static int MAXN = 501;

    public static int MAXM = 51;

    public static int[][][] dp = new int[MAXN][MAXM][2];

    public static int[] next = new int[MAXM];

    public static void clear(int n, int m) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dp[i][j][0] = -1;
                dp[i][j][1] = -1;
            }
        }
    }

    /**
     * @param n    字符串长度
     * @param str1 目标字符串的字典序大于我
     * @param str2 目标字符串的字典序小于我
     * @param evil 目标字符串中不能包含这个字串
     * @return 满足条件的字符串数量
     */
    public static int findGoodStrings(int n, String str1, String str2, String evil) {
        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();
        char[] e = evil.toCharArray();

        int m = e.length;

        nextArray(e, m);
        clear(n, m);
        // <= s2的好字符串数量
        int ans = f(s2, e, n, m, 0, 0, 0);
        clear(n, m);
        // 减去<=s1的好字符串数量
        ans = (ans - f(s1, e, n, m, 0, 0, 0) + MOD) % MOD;
        if (kmp(s1, e, n, m) == -1) {
            ans = (ans + 1) % MOD;
        }

        return ans;
    }

    /**
     * @param s    生成的字符串的字典序不大于我
     * @param e    生成的字符串中没有我这个子串
     * @param n    s.length
     * @param m    e.length
     * @param i    0...i-1的部分已经做了决策
     * @param j    匹配出了e[0...j-1]的部分
     * @param free 1-前面权重比较大的位置已经保证比s小了, 0 相反情况
     * @return 匹配出的数量
     */
    private static int f(char[] s, char[] e, int n, int m, int i, int j, int free) {
        if (j == m) {
            // 一旦配出了e的整体
            // 说明之前的决策已经违规
            // 后续有效决策数量0
            return 0;
        }

        if (i == n) {
            // 说明所有决策已做完，并且不含有e字串
            // 同时决策的每一步都保证了不会比s大
            // 返回一种有效决策（之前做的所有决定）
            return 1;
        }

        if (dp[i][j][free] != -1) {
            // 已经走过的分支直接返回结果
            return dp[i][j][free];
        }
        // 获取上限字符串当前位置字符
        char cur = s[i];
        int ans = 0;
        if (free == 0) {
            // 之前的决策和s的状况
            // 当前尝试比cur小的字符
            for (char pick = 'a'; pick < cur; pick++) {
                ans = (ans + f(s, e, n, m, i + 1, jump(pick, e, j) + 1, 1)) % MOD;
            }
            // 当前尝试=cur的字符
            ans = (ans + f(s, e, n, m, i + 1, jump(cur, e, j) + 1, 0)) % MOD;
        } else {
            // 之前的决策已经保证高权值位比s字符串小
            // 当前在a~z范围随便尝试
            for (char pick = 'a'; pick <= 'z'; pick++) {
                ans = (ans + f(s, e, n, m, i + 1, j, 1)) % MOD;
            }
        }
        dp[i][j][free] = ans;
        return ans;
    }

    /**
     * @param pick 当前尝试的字符
     * @param e    不能包含的字符串
     * @param j    e[0...j-1]已经包含的部分
     * @return 目标字符串当前位置放pick字符后，j的新位置
     */
    private static int jump(char pick, char[] e, int j) {
        while (j >= 0 && pick != e[j]) {
            j = next[j];
        }

        return j;
    }

    private static void nextArray(char[] e, int m) {
        next[0] = -1;
        next[1] = 0;

        int i = 2, cn = 0;
        while (i < m) {
            if (e[i - 1] == e[cn]) {
                next[i++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[i++] = 0;
            }
        }
    }

    private static int kmp(char[] s, char[] e, int n, int m) {
        int x = 0, y = 0;

        while (x < n && y < m) {
            if (s[x] == e[y]) {
                x++;
                y++;
            } else if (y == 0) {
                x++;
            } else {
                y = next[y];
            }
        }
        return y == m ? x - y : -1;
    }
}
